# -*- coding: utf-8 -*-
# author: AZJ
# date: 2024/11/13
# 假如命运扼住了你的咽喉，你就去挠她的咯吱窝
# 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # 1. 设立一个dp[i][j]表示到(i,j)所需要的最小数字
        # 2. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
        # 3. 初始化：第一行与第一列, dp[0][j] = grid[0][j]; dp[i][0] = grid[i][0]
        y = len(grid)
        x = len(grid[0])
        dp = [[0]*x for _ in range(y)]
        dp[0][0] = grid[0][0]
        for i in range(y):
            for j in range(x):
                if i == 0 and j != 0:
                    dp[i][j] = grid[i][j] + dp[i][j-1]
                if j == 0 and i != 0:
                    dp[i][j] = grid[i][j] + dp[i-1][j]
        # print(dp)
        for i in range(1, y):
            for j in range(1, x):
                dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
        # print(dp)
        return dp[-1][-1]


if __name__ == '__main__':
    solution = Solution()
    print(solution.minPathSum([[1,2,3],[4,5,6]]))